package com.sourcetrip.algorithm.sort.count;

import com.sourcetrip.algorithm.abs.AbstractCustomedObjectSort;
import com.sourcetrip.utils.Integers;

import java.util.Arrays;

/**
 * @author: ZhouBert
 * @date: 2021/1/4
 * @description: 十大排序算法之七：计数排序（的对象比较版本，并不能比较自定义对象） --
 * 在 V0 上进行优化：
 * 1.保证稳定性；
 * 2.负整数也可以进行排序；
 * --
 * 严格来说并不是说完全不能用自定义对象，条件是 该对象的整型字段被用来排序！
 */
public class CountCustomedSortV1 extends AbstractCustomedObjectSort<Integer> {

	/**
	 * 核心思想是构造一个中间数组 record
	 * 【让 record 中 i 代表的值放在 newArray[record[i]-1] 的位置上】
	 * @param objectArr
	 */
	@Override
	protected void sortArr(Integer[] objectArr) {
		//1.找到 min max
		int min = objectArr[0], max = min;
		for (int i = 1; i < objectArr.length; i++) {
			min = Math.min(objectArr[i], min);
			max = Math.max(objectArr[i], max);
		}
		//2.根据 min + max 创建记录数组
		int[] record = new int[max - min + 1];
		for (int i = 0; i < objectArr.length; i++) {
			//记录索引的规律：objectArr[i]-min（eg.0 的位置存储 min 的次数）
			record[objectArr[i] - min]++;
		}

		//3.重新构造 record 数组，为稳定排序做铺垫！
		//新 record 满足以下规律：
		//record(new)[i] = record(old)[i-1] + record(old)[i]
		for (int i = 1; i < record.length; i++) {
			record[i] = record[i] + record[i - 1];
		}

		//4.创建一个跟 objectArr 同长度的数组 newArr；
		//从尾到头遍历 objectArr，根据 record 将数据填进 newArr
		int[] newArr = new int[objectArr.length];
		for (int i = objectArr.length - 1; i >= 0; i--) {
			//精髓，这就是 重构 record 的意义！
			newArr[--record[objectArr[i] - min]] = objectArr[i];
		}

		//5.此时 newArr 是对原数组已经排好序的数组，于是进行覆盖即可。
		for (int i = 0; i < newArr.length; i++) {
			objectArr[i] = newArr[i];
		}
	}

	public static void main(String[] args) {
		CountCustomedSortV1 sortV1 = new CountCustomedSortV1();
		Integer[] random = Integers.random(10, 10, 100);
		random = new Integer[]{5, 4, 3, 2, 1};
		random = Integers.random(100, 10, 100);
		sortV1.sortArr(random);
		System.out.println(Arrays.toString(random));
	}
}
